Improving performance of a computer program, i.e., shortening its running time, has been one of the main objectives in the computer research since the inception of the computer. The use of compilers has proven to be one of the most effective ways to improve computer performance. Over the past several decades, many compilation techniques have been developed for performing this task. Examples of compilers for optimizing computational performance are described in U.S. Pat. No. 6,078,744 issued to Wolczko, et al. and U.S. Pat. No. 5,659,754 issued to Grove, et al. Both of the aforementioned U.S. patents are incorporated herein by reference for all purposes.
A compiler is a software program that translates source code into the machine code that can be executed on a computer. There are many ways to generate using a compiler. Some compilations result in faster code, while other compilations result in slower code. Compiler optimizations are techniques to generate faster code. Some optimizations, such as “inlining” of procedure calls and “hoisting” of loop invariant code, need to be applied on frequently executed code segments. However, if those optimizations are applied on infrequent executed code segments, performance can actually be degraded. Furthermore, applying optimizations also increases compiling time, which decreases productivity. Thus, a compiler should avoid unnecessary optimizations, such as those that apply to infrequently executed code segments.
A “profile” is a well-known technique that tells a compiler which code segments are frequently executed and which are not. In the field of compilers, the optimizations based on profiles are known as profile-directed optimizations (PDO) or feedback-directed optimizations (FDO). Further discussion of these techniques can be found in: 1) Pohua P. Chang, Scott A. Mahlke, and Wen-Mei W. Hwu, “Using Profile Information to Assist Classic Code Optimizations, Software—Practice and Experience,” Vol. 21(12), 1301-1321, December 1991; and 2) Thomas Ball, James R. Larus, “Optimally Profiling and Tracing Programs, ACM Transactions on Programming Languages and Systems,” Vol. 16, No. 4, July 1994, 1319-1360. Each of the aforementioned references is hereby incorporated by reference for all purposes.
There are many PDO techniques, including “procedure inlining” and “code reordering.” In general, procedure inlining replaces a call statement (also referred to as “call site” or simply “call”) with the corresponding called procedure, usually referred to as the “callee.” Procedure inlining offers the advantage of eliminating call overhead and providing better opportunities for optimizations. The disadvantage of inlining is that it may increase compiling time and code size. Inlining also may degrade runtime performance if infrequently executed calls are inlined, or if inlining causes more register spills as a result of high register pressure.
Profile-directed procedure inlining selects calls to inline based on their execution frequencies. The goal is to select frequently executed calls and avoid infrequently executed calls. Profile-directed reordering of code segments based on their frequencies is also widely used. In this method, the most frequently executed segments are grouped together to achieve better locality and thus improve performance.
Because PDOs rely on frequency to make optimization decisions, the accuracy of frequency is essential. Some PDOs change frequency and, therefore, if the frequency is not updated after a frequency changing optimization is performed, other profile-directed optimizations carried out afterwards will rely on inaccurate frequency. This can result in unwanted optimizations that degrade performance. Among these PDOs, procedure inlining is a technique that changes frequency significantly. It is essential, therefore, that a procedure inlining optimization is accompanied by an accurate frequency updating technique.